package algocasts;

public class P134_ImportantReversePairs {
    private void merge(int[] arr, int low, int mid, int high, int[] tmp) {
        int i = low, j = mid + 1, k = 0;
        while (i <= mid && j <= high) {
            if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
            else tmp[k++] = arr[j++];
        }
        while (i <= mid) tmp[k++] = arr[i++];
        while (j <= high) tmp[k++] = arr[j++];
        System.arraycopy(tmp, 0, arr, low, k);
    }

    private int count(int[] arr, int low, int mid, int high) {
        int i = low, j = mid + 1, cnt = 0;
        while (i <= mid && j <= high) {
            if (arr[i] <= 2L * arr[j]) {
                ++i;
            } else {
                cnt += (mid - i + 1);
                ++j;
            }
        }
        return cnt;
    }

    private int sortAndCount(int[] arr, int low, int high, int[] tmp) {
        int cnt = 0;
        if (low < high) {
            int mid = low + (high - low) / 2;
            cnt += sortAndCount(arr, low, mid, tmp);
            cnt += sortAndCount(arr, mid + 1, high, tmp);
            cnt += count(arr, low, mid, high);
            merge(arr, low, mid, high, tmp);
        }
        return cnt;
    }

    // Time: O(n*log(n))  Space: O(n)
    public int reversePairsMergeSort(int[] nums) {
        if (nums == null || nums.length < 2) return 0;
        int[] tmp = new int[nums.length];
        return sortAndCount(nums, 0, nums.length - 1, tmp);
    }
}
